#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
class Solution {
public:
    int difference(const string& s1, const string& s2)
    {
        int count = 0;
        for (int i = 0; i < s1.size(); i++)
        {
            if (s1[i] != s2[i])
                ++count;
        }
        return count;
    }
    int ladderLength(string beginWord, string endWord, vector<string>& wordList)
    {
        if (beginWord == endWord)
            return 0;
        int n = wordList.size();
        vector<bool> sta(n, false);
        queue<string> q;
        q.push(beginWord);
        int count = 1;
        while (!q.empty())
        {
            int cnt = q.size();
            ++count;
            //cout<<count<<endl;
            while (cnt--)
            {
                string s = q.front();
                q.pop();
                for (int i = 0; i < n; i++)
                {
                    if (sta[i] == false && difference(s, wordList[i]) == 1 &&
                        wordList[i] != beginWord)
                    {
                        //cout << wordList[i] << endl;
                        if (wordList[i] == endWord)
                            return count;
                        q.push(wordList[i]);
                        sta[i] = true;
                    }
                }
            }
        }
        return 0;

    }
};